package datastructure.tree.avl;

import java.util.ArrayList;
import java.util.List;

/**
 * @Description: 平衡二叉树
 * @author: Yang Qiang
 * @create: 2021-12-15 22:20
 */
public class AVLTree<E extends Comparable<E>> {

    // 树的根节点
    private Node root;
    // 树的节点个数
    private int size;

    /**
     * AVL树的两个条件之一
     * 1: BST
     * 如何判断一颗树是不是搜索二叉树呢. 我们可以中序遍历, 然后看遍历出来的数据是否是从小到大
     */
    public boolean isBST(){
        // 保存中序遍历结果
        List<E> eList = new ArrayList<>();
        // 中序遍历
        minOrder(eList);
        // 判断遍历结果是否有序
        for (int i = 1; i < eList.size(); i++){
            if (eList.get(i - 1).compareTo(eList.get(i)) >0){
                // 前面的数比后面的数大, 那么就不是BST
                return false;
            }
        }
        return true;
    }

    /**
     * AVL树的两个条件之一
     * 2: 平衡
     * 判断: 任意一个节点，平衡因子的绝对值不超过1
     */
    public boolean isBalance(){
        // 从根节点开始判断
        return isBalance(root);
    }
    // 判断一个节点的平衡因子的绝对值是否不超过1
    private boolean isBalance(Node node) {
        if (node == null) return true;
        // 得到节点的平衡因子
        int bf = getBalanceFactor(node);
        if (Math.abs(bf) > 1){
            return false;
        }
        // 递归的判断左右子节点, 直到为null
        return isBalance(node.left) && isBalance(node.right);
    }
    // 得到一个节点的平衡因子
    private int getBalanceFactor(Node node) {
        if (node == null) return 0;
        // 左子树的高度减去右子树的高度
        return getHeight(node.left) - getHeight(node.right);
    }
    // 得到一个节点的高度
    private int getHeight(Node node) {
        if (node == null)return 0;
        // 直接返回我们维护的节点高度
        return node.height;
    }


    // 深度优先-中序遍历
    public void minOrder(List<E> eList){
        minOrder(root, eList);
    }
    /**
     * 以node为根节点的二叉搜索树的中序遍历
     * @param node
     */
    private void minOrder(Node node, List<E> eList) {
        if (node == null) return;
        // 先遍历左子树
        minOrder(node.left, eList);
        // 再输出父节点
        eList.add(node.e);
        // 再遍历右子树
        minOrder(node.right, eList);

    }

    // 添加节点, 构建BST树
    public void addEle(E e){
        this.root = addEle(root, e);
    }
    /**
     * 将元素e插入到以node为根节点的子树
     * @param node
     * @param e
     * @return: 新插入了元素e以后新数的根
     */
    private Node addEle(Node node, E e){
        // 如果是一个空树 || 递归到最后一个没有子节点的节点
        if (node == null){
            size++;
            return new Node(e);
        }
        // 如果树里面有元素
        if (e.compareTo(node.e) < 1){// 如果添加的元素比节点小就插入左边, 但是左边需要一直递归
            node.left = addEle(node.left, e);
        }else {// 如果添加的元素大于等于节点就插入右边, 但是右边需要一直递归
            node.right = addEle(node.right, e);
        }
        return node;
    }

    // 返回树的节点数
    public int getSize() {
        return size;
    }

    // 树节点定义
    public class Node{
        // 节点的数据
        public E e;
        // 节点的左节点
        public Node left;
        // 节点的右节点
        public Node right;
        // 节点的高度
        public int height;

        public Node(E e) {
            this.e = e;
            this.left = null;
            this.right = null;
            this.height = 1;
        }
        public Node() {
        }
        @Override
        public String toString() {
            return e + "";
        }
    }
}
